import java.util.*;

public class Solution {
    // 第 N 个泰波那契数
    public int tribonacci(int n) {
        // 处理特殊情况
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        // 创建dp表
        int[] dp = new int[n + 1];
        // 初始化
        dp[0] = 0;
        dp[1] = dp[2] = 1;
        // 填表
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        // 返回
        return dp[n];
    }

    // 第 N 个泰波那契数 —— 滚动数组优化
    public int tribonacci2(int n) {
        // 处理特殊情况
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int x = 0, y = 1, z = 1, r = 0;
        for(int i = 3; i <= n; i++) {
            r = x + y + z;
            x = y;
            y = z;
            z = r;
        }
        return r;
    }

    // 三步问题
    public int waysToStep(int n) {
        // 处理特殊情况
        if (n <= 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }
        // 创建 dp 表
        int[] dp = new int[n + 1];
        // 初始化
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        // 填表
        for (int i = 4; i <= n; i++) {
            dp[i] = ((dp[i - 3] + dp[i - 2]) % 1000000007 + dp[i - 1]) % 1000000007;
        }
        // 返回
        return dp[n];
    }

    // 三步问题 —— 滚动数组优化
    public int waysToStep2(int n) {
        // 处理特殊情况
        if (n <= 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }
        int x = 1, y = 2, z = 4, r = 0;
        // 填表
        for (int i = 4; i <= n; i++) {
            r = ((x + y) % 1000000007 + z) % 1000000007;
            x = y;
            y = z;
            z = r;
        }
        // 返回
        return r;
    }

    // 使用最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        // 创建 dp 表
        int[] dp = new int[n + 1];
        // 初始化
        // 填表
        for(int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }
        return dp[n];
    }

    // 使用最小花费爬楼梯 —— 滚动数组优化
    public int minCostClimbingStairs2(int[] cost) {
        int n = cost.length;
        // 创建 dp 表
        // int[] dp = new int[n + 1];
        // 初始化
        int x = 0, y = 0, z = 0;
        // 填表
        for(int i = 2; i <= n; i++) {
            z = Math.min(x + cost[i - 2], y + cost[i - 1]);
            x = y;
            y = z;
        }
        return z;
    }

    // 解码方法
    public int numDecodings(String s) {
        int n = s.length();
        char[] chs = s.toCharArray();
        // 创建dp表
        int[] dp = new int[n + 1];
        // 初始化
        if (chs[0] > '0') {
            dp[0] = 1;
        } else {
            return 0;
        }

        // 处理特殊情况
        if (n == 1) {
            return 1;
        }

        // 填表
        for (int i = 1; i < n; i++) {
            if (chs[i] - '0' > 0) {
                dp[i] = dp[i - 1];
            }
            int x = (chs[i - 1] - '0') * 10 + (chs[i] - '0');
            if (x >= 10 && x <= 26) {
                if (i == 1) {
                    dp[i] += 1;
                } else {
                    dp[i] += dp[i - 2];
                }

            }
        }
        // 返回
        return dp[n - 1];
    }

    // 不同路径
    public int uniquePaths(int m, int n) {
        // 创建 dp 表
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        dp[0][1] = 1;
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    // 不同路径2
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // 创建dp表
        int[][] dp = new int[m+1][n+1];
        // 初始化
        dp[0][1] = 1;
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(obstacleGrid[i - 1][j - 1] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    // 珠宝的最高价值
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        // 创建dp表
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        for(int j = 1; j <= n; j++) {
            dp[0][j] = Integer.MIN_VALUE;
        }
        for(int i = 1; i <= m; i++) {
            dp[i][0] = Integer.MIN_VALUE;
        }
        dp[0][1] = 0;
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        // 返回
        return dp[m][n];
    }

    // 下降路径最小和
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 创建dp表
        int[][] dp = new int[m+1][n+2];
        // 初始化
        for(int i = 1; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n + 1] = Integer.MAX_VALUE;
        }
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
            }
        }
        // 返回
        int res = dp[m][1];
        for(int j = 2; j <= n; j++) {
            res = Math.min(res, dp[m][j]);
        }
        return res;
    }

    // 最小路径和
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 创建dp表
        int[][] dp = new int[m+1][n+1];
        // 初始化
        for(int i = 1; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for(int j = 1; j <= n; j++) {
            dp[0][j] = Integer.MAX_VALUE;
        }
        dp[0][1] = 0;
        // 填表
        for (int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

    // 地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        // 创建 dp 表
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        for(int i = 0; i < m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        for(int j = 0; j < n; j++) {
            dp[m][j] = Integer.MAX_VALUE;
        }
        dp[m][n - 1] = 1;
        // 填表
        for(int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }

    // 按摩师
    public int massage(int[] nums) {
        int n = nums.length;
        if (n <= 0) {
            return n;
        }
        // 创建 dp 表
        int[] f = new int[n];
        int[] g = new int[n];
        // 初始化
        f[0] = nums[0];
        // 填表
        for(int i = 1; i < n; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[n - 1], g[n - 1]);
    }

    // 打家劫舍II
    public int rob(int[] nums) {
        int n = nums.length;
        // 处理特殊情况
        if (n <= 1) {
            return nums[0];
        }
        // 计算 0 - n-2
        int res1 = dp(nums, 0, n - 2);
        // 计算 0 - n-1
        int res2 = dp(nums, 1, n - 1);
        return Math.max(res1, res2);
    }
    public int dp(int[] nums, int left, int right) {
        // 创建 dp 表
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        // 初始化
        f[left] = nums[left];
        // 填表
        for (int i = left + 1; i <= right; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(g[right], f[right]);
    }

    // 删除并获得点数
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int[] hash = new int[10001];
        // 初始化 hash 表
        for(int i = 0; i < n; i++) {
            hash[nums[i]] += nums[i];
        }
        // 创建 dp 表
        int[] f = new int[hash.length];
        int[] g = new int[hash.length];
        // 初始化
        f[0] = hash[0];
        for(int i = 1; i < hash.length; i++) {
            f[i] = g[i - 1] + hash[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[hash.length - 1], g[hash.length - 1]);
    }

    public int deleteAndEarn2(int[] nums) {
        int n = nums.length;
        int max = nums[0];
        for(int x: nums) {
            max = Math.max(max, x);
        }
        int[] hash = new int[max + 1];
        // 初始化 hash 表
        for(int i = 0; i < n; i++) {
            hash[nums[i]] += nums[i];
        }
        // 创建 dp 表
        int[] f = new int[hash.length];
        int[] g = new int[hash.length];
        // 初始化
        f[0] = hash[0];
        for(int i = 1; i < hash.length; i++) {
            f[i] = g[i - 1] + hash[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[hash.length - 1], g[hash.length - 1]);
    }

    // 粉刷房子
    public int minCost(int[][] costs) {
        int n = costs.length;
        // 创建 dp 表
        int[][] dp = new int[n][3];
        // 初始化 dp 表
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];
        // 填表
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
        }
        return Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
    }

    // 买卖股票的最佳时机含冷冻期
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // 创建 dp 表
        int[][] dp = new int[n][3];
        // 初始化
        dp[0][0] = -prices[0];
        // 填表
        for(int i = 1; i < n; i++) {
            // 买入
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
            // 冷冻
            dp[i][1] = dp[i - 1][0] + prices[i];
            // 可交易
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]);
        }
        // 返回
        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }

    // 买卖股票的最佳时机含手续费
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        // 创建 dp 表
        int[][] dp = new int[n][2];
        // 初始化
        dp[0][0] = -prices[0];
        // 填表
        for(int i = 1; i < n; i++) {
            // 买入后
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            // 卖出后
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
        }
        // 返回
        return dp[n - 1][1];
    }

    // 买卖股票的最佳时机I(贪心)
    public int maxProfitI(int[] prices) {
        int n = prices.length;
        int minPrice = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                max = Math.max(max, prices[i] - minPrice);
            }
        }
        return max;
    }

    // 买卖股票的最佳时机II(动态规划)
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = -prices[0];
        for(int i = 1; i < n; i++) {
            f[i] = Math.max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = Math.max(g[i - 1], f[i - 1] + prices[i]);
        }
        // return Math.max(f[n - 1], g[n - 1]);
        return g[n - 1];
    }

    // 买卖股票的最佳时机II(贪心)
    public int maxProfitII(int[] prices) {
        int n = prices.length;
        int res = 0;
        int[] p = Arrays.copyOf(prices, n + 1);
        int minPrice = p[0];
        int maxPrice = 0;
        // System.out.println(minPrice);
        for (int i = 1; i < n - 1; i++) {
            // 上升到最大值
            if (p[i] >= p[i - 1] && p[i] > p[i + 1]) {
                res += (p[i] - minPrice);
            }
            // 下降到最小值
            if (p[i] < p[i - 1] && p[i] <= p[i + 1]) {
                minPrice = p[i];
                // System.out.println(minPrice);
            }
        }
        return res;
    }

    public int maxProfit22(int[] prices) {
        int n = prices.length;
        int res = 0;
        for (int i = 1; i < n; i++) {
            res += Math.max(prices[i] - prices[i - 1], 0);
        }
        return res;
    }

    // 买卖股票的最佳时机III
    public int maxProfitIII(int[] prices) {
        int n = prices.length;
        // 创建 dp 表
        int k = 2;
        // 买入
        int[][] f = new int[n][k + 1];
        // 卖出
        int[][] g = new int[n][k + 1];
        // 初始化
        int INF = 0x3f3f3f3f;
        for(int j = 0; j <= k; j++) {
            f[0][j] = -INF;
            g[0][j] = -INF;
        }
        g[0][0] = 0;
        f[0][0] = -prices[0];
        // 填表
        for(int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                // 当前买入
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                // 当前卖出
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int max = g[n - 1][0];
        for(int i = 1; i <= k; i++) {
            max = Math.max(max, g[n - 1][i]);
        }
        return max;
    }

    // 买卖股票的最佳时机IV
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        // 创建 dp 表
        // 优化
        k = Math.min(k, n / 2);
        // 买入
        int[][] f = new int[n][k + 1];
        // 卖出
        int[][] g = new int[n][k + 1];
        // 初始化
        int INF = 0x3f3f3f3f;
        for(int j = 0; j <= k; j++) {
            f[0][j] = -INF;
            g[0][j] = -INF;
        }
        g[0][0] = 0;
        f[0][0] = -prices[0];
        // 填表
        for(int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                // 当前买入
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                // 当前卖出
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int max = g[n - 1][0];
        for(int i = 1; i <= k; i++) {
            max = Math.max(max, g[n - 1][i]);
        }
        return max;
    }

    // 最大子数组和
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        // 创建 dp 表
        int[] dp = new int[n];
        // 初始化
        dp[0] = nums[0];
        int max = dp[0];
        // 填表
        for(int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            max = Math.max(dp[i], max);
        }
        return max;
    }

    // 环形数组的最大和
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        // 创建 dp 表
        int[] f = new int[n];
        int[] g = new int[n];
        // 初始化
        f[0] = g[0] = nums[0];
        int sum = nums[0];
        int min = g[0];
        int max = f[0];
        // 填表
        for(int i = 1; i < n; i++) {
            f[i] = Math.max(f[i - 1] + nums[i], nums[i]);
            g[i] = Math.min(g[i - 1] + nums[i], nums[i]);
            sum += nums[i];
            min = Math.min(g[i], min);
            max = Math.max(f[i], max);
        }
        // System.out.println("sum:" + sum + " min:" + min + " max:" + max);
        if (sum - min == 0) {
            return max;
        }
        return Math.max(sum - min , max);
    }

    // 乘积最大子数组
    public int maxProduct(int[] nums) {
        int n = nums.length;
        // 创建 dp 表
        int[] f = new int[n + 1]; // 最大值
        int[] g = new int[n + 1]; // 最小值
        // 初始化
        f[0] = g[0] = 1;
        int res = nums[0];
        // 填表
        for(int i = 1; i <= n; i++) {
            int x = nums[i - 1] * f[i - 1];
            int y = nums[i - 1] * g[i - 1];
            f[i] = Math.max(nums[i - 1], Math.max(x, y));
            g[i] = Math.min(nums[i - 1], Math.min(x, y));
            res = Math.max(res, f[i]);
        }
        return res;
    }

    // 乘积为正数的最长子数组长度
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        // 创建 dp 表
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        // 初始化
        int res = 0;
        // 填表
        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] > 0) {
                g[i] = (g[i - 1] == 0 ? 0: g[i - 1] + 1);
                f[i] = f[i - 1] + 1;
                // g[i] = g[i - 1] + 1;
            } else if (nums[i - 1] < 0) {
                f[i] = (g[i - 1] == 0 ? 0: g[i - 1] + 1);
                // f[i] = g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            } else {
                f[i] = g[i] = 0;
            }
            // System.out.println(i + " f[i]:" + f[i] + " g[i]:" + g[i]);
            res = Math.max(res, f[i]);
        }
        return res;
    }

    // 等差数列划分
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        // 处理特殊情况
        if (n <= 2) {
            return 0;
        }
        // 创建 dp 表
        int[] dp = new int[n];
        // 初始化
        int res = 0;
        // 填表
        for(int i = 2; i < n; i++) {
            if (nums[i] + nums[i - 2] == 2 * nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            res += dp[i];
        }
        return res;
    }

    // 最长湍流子数组
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        // 创建 dp 表
        int[] f = new int[n]; // 呈上升趋势
        int[] g = new int[n]; // 呈下降趋势
        // 初始化
        for(int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
        }
        int res = 1;
        // 填表
        for(int i = 1; i < n; i++) {
            if (arr[i] - arr[i - 1] > 0) {
                f[i] = g[i - 1] + 1;
            } else if(arr[i] - arr[i - 1] < 0) {
                g[i] = f[i - 1] + 1;
            }
            res = Math.max(res, Math.max(f[i], g[i]));
        }
        return res;
    }

    // 单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        // 将单词放到 set 中
        Set<String> set = new HashSet<>();
        for(String word: wordDict) {
            set.add(word);
        }
        s = " " + s;
        int n = s.length();
        // 创建 dp 表
        boolean[] dp = new boolean[n];
        // 初始化
        dp[0] = true;
        // 填表
        for(int i = 1; i < n; i++) {
            for(int j = i; j > 0; j--) {
                if (dp[j - 1] && set.contains(s.substring(j, i + 1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n - 1];
    }

    // 环绕字符串中唯一的子字符串
    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        if (n <= 1) {
            return n;
        }
        // 创建 dp 表
        int[] dp = new int[n];
        // 初始化
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        int res = 0;
        // 填表
        for(int i = 1; i < n; i++) {
            int index = s.charAt(i);
            int preIndex = s.charAt(i - 1);
            if ((s.charAt(i) == 'a' && s.charAt(i - 1) == 'z') || (index - preIndex == 1)) {
                dp[i] += dp[i - 1];
            }
            //  res += dp[i];
        }
        // 去重
        int[] hash = new int[26];
        for(int i = 0; i < n; i++) {
            hash[s.charAt(i) - 'a'] = Math.max(hash[s.charAt(i) - 'a'], dp[i]);
        }
        for(int x: hash) {
            res += x;
        }
        return res;
    }

    // 最长递增子序列
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // 创建 dp 表
        int[] dp = new int[n];
        // 初始化
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        int max = dp[0];
        // 填表
        for(int i = 1; i < n; i++) {
            for(int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        // 返回
        return max;
    }

    // 摆动序列
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        // 创建 dp 表
        int[] f = new int[n];
        int[] g = new int[n];
        // 初始化
        for(int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
        }
        int max = f[0];
        // 填表
        for(int i = 1; i < n; i++) {
            for(int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) { // 递增
                    f[i] = Math.max(f[i], g[j] + 1);
                }
                if (nums[i] < nums[j]) { // 递减
                    g[i] = Math.max(g[i], f[j] + 1);
                }
                max = Math.max(max, Math.max(f[i], g[i]));
            }
            // System.out.println(i + " f[i]: " + f[i] + " g[i]: " + g[i]);
        }
        return max;
    }

    // 最长递增子序列的个数
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        // 创建 dp 表
        int[] dp = new int[n]; // 最长递增子序列长度
        int[] count = new int[n]; // 最长递增子序列个数
        // 初始化
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
            count[i] = 1;
        }
        int max = dp[0];
        int num = 0;
        // 填表
        for(int i = 1; i < n; i++) {
            for(int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        for(int i = 0; i < n; i++) {
            if (dp[i] == max) {
                num += count[i];
            }
        }
        // 返回
        return num;
    }

    // 最长数对链
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        // 预处理，对数组进行排序
        Arrays.sort(pairs, (a, b) -> {
            return a[0] - b[0];
        });
        // System.out.println(Arrays.deepToString(pairs));
        // 创建 dp 表
        int[] dp = new int[n];
        // 初始化
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        int maxLen = 1;
        // 填表
        for(int i = 1; i < n; i++) {
            for(int j = i - 1; j >= 0; j--) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(dp[i], maxLen);
        }
        return maxLen;
    }

    // 最长定差子序列
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        // 预处理
        Map<Integer, Integer> hash = new HashMap<>();
        // 创建 dp 表
        int[] dp = new int[n];
        // 初始化
        int maxLen = 1;
        // 填表
        for(int i = 0; i < n; i++) {
            dp[i] = hash.getOrDefault(arr[i] - difference, 0) + 1;
            hash.put(arr[i], dp[i]);
            maxLen = Math.max(dp[i], maxLen);

        }
        return maxLen;
    }

    // 最长的斐波那契子数列的长度
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        // 预处理
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < n; i++) {
            hash.put(arr[i], i);
        }
        // 创建 dp 表
        int[][] dp = new int[n][n];
        // 初始化
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        int max = 2;
        // 填表
        for(int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (hash.containsKey(arr[j] - arr[i])) {
                    int k = hash.get(arr[j] - arr[i]);
                    if (k < i) {
                        dp[i][j] = dp[k][i] + 1;
                    }
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max < 3 ? 0: max;
    }

    // 最长等差数列
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        // 预处理
        Map<Integer, Integer> hash = new HashMap<>();
        // 可能会存在重复元素，若要先存，则需要存放下标数组
        // for(int i = 0; i < n; i++) {
        //     hash.put(nums[i], i);
        // }
        hash.put(nums[0], 0);
        // 创建 dp 表
        int[][] dp = new int[n][n];
        // 初始化
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        int max = 2;
        // 填表
        for(int i = 1; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                int a = nums[i] * 2 - nums[j];
                if (hash.containsKey(a)) {
                    int k = hash.get(a);
                    dp[i][j] = dp[k][i] + 1;
                    max = Math.max(dp[i][j], max);
                    // System.out.println(dp[k][i]);
                    // System.out.println("i: " + i + " j: " + j + " dp[i][j]:" + dp[i][j]);
                }
            }
            hash.put(nums[i], i);
        }
        return max;
    }

    // 等差数量划分II - 子序列
    public int numberOfArithmeticSlices2(int[] nums) {
        int n = nums.length;
        // 预处理
        Map<Long, List<Integer>> hash = new HashMap<>(); // 防止越界
        for (int i = 0; i < n; i++) {
            if (!hash.containsKey((long)nums[i])) {
                hash.put((long)nums[i], new ArrayList<Integer>());
            }
            hash.get((long)nums[i]).add(i);
        }
        // for(Long key: hash.keySet()) {
        //     System.out.println("list: " + hash.get(key).toString());
        // }
        // 创建 dp 表
        int[][] count = new int[n][n]; // 数量
        // 初始化
        int sum = 0;
        // 填表
        for(int i = 1; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                long a = (long)nums[i] * 2 - nums[j];
                if (hash.containsKey(a)) {
                    List<Integer> list = hash.get(a);
                    //  System.out.println("list: " + list.toString());
                    for(int k: list) {
                        if (k < i) {
                            count[i][j] += count[k][i] + 1;
                        } else {
                            break;
                        }
                    }
                }
                sum += count[i][j];
                //   System.out.println("i: " + i + " j: " + j + "count[i][j] " + count[i][j]);
            }
        }
        return sum;
    }


    // 回文子串
    public int countSubstrings(String s) {
        int n = s.length();
        // 创建 dp 表
        boolean[][] dp = new boolean[n][n];
        int count = 0;
        // 填表
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || i + 1 == j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }

    // 最长回文子串
    public String longestPalindrome(String s) {
        int n = s.length();
        // 创建 dp 表
        boolean[][] dp = new boolean[n][n];
        // 初始化
        int beginIndex = 0;
        int endIndex = 0;
        // 填表
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                //   System.out.println("i: " + i + " j: " + j);
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || i + 1 == j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && (j - i + 1) > (endIndex - beginIndex + 1)) {
                    beginIndex = i;
                    endIndex = j;
                    //  System.out.println("begin: " + beginIndex + " end: " + endIndex);
                }
            }
        }
        return s.substring(beginIndex, endIndex + 1);
    }

    // 分割回文串IV
    public boolean checkPartitioning(String s) {
        int n = s.length();
        // 创建 dp 表
        boolean[][] dp = new boolean[n][n];
        // 填表
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || i + 1 == j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }
        // 判断
        for (int i = 1; i < n - 1; i++) {
            for(int j = i; j < n - 1; j++) {
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) {
                    return true;
                }
            }
        }
        return false;
    }

    // 分割回文串II
    public int minCut(String s) {
        int n = s.length();
        // 创建 dp 表
        boolean[][] dp = new boolean[n][n];
        // 填表
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || i + 1 == j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }
        // 求划分次数
        int[] count = new int[n];
        // 初始化
        for(int i = 0; i < n; i++) {
            count[i] = n;
        }
        for(int i = 0; i < n; i++){
            if(dp[0][i]) {
                count[i] = 0;
            } else {
                for(int j = 1; j <= i; j++) {
                    if(dp[j][i]) {
                        count[i] = Math.min(count[i], count[j - 1] + 1);
                    }
                }
            }
        }
        return count[n - 1];
    }

    // 最长回文子序列
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // 创建 dp 表
        int[][] dp = new int[n][n];
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j) {
                        dp[i][j] = 1;
                    } else if (i + 1 == j) {
                        dp[i][j] = 2;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }

//    让字符串称为回文串的最小插入次数
    public int minInsertions(String s) {
        int n = s.length();
        // 创建 dp 表
        int[][] dp = new int[n][n];
        // 初始化
        // 填表
        for(int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i != j && i + 1 != j) {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }

    // 最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        // 创建 dp 表
        int[][] dp = new int[m + 1][n + 1];
        text1 = " " + text1;
        text2 = " " + text2;
        // 初始化
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    // 不相交的线
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 创建 dp 表
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    // 不同的子序列
    public int numDistinct(String s, String t) {
        int m = t.length();
        int n = s.length();
        s = " " + s;
        t = " " + t;
        // 创建 dp 表
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        for(int j = 0; j <= n; j++) {
            dp[0][j] = 1;
        }
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if (s.charAt(j) == t.charAt(i)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                dp[i][j] += dp[i][j - 1];
                dp[i][j] %= 1000000000 + 7;
            }
        }
        return dp[m][n];
    }

    // 通配符匹配
    public boolean isMatch(String s, String p) {
        int m = p.length();
        int n = s.length();
        s = " " + s;
        p = " " + p;
        // 创建 dp 表
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 初始化
        dp[0][0] = true;
        for(int i = 1; i <= m; i++) {
            if (p.charAt(i) == '*') {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if (p.charAt(i) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = (p.charAt(i) == s.charAt(j) || p.charAt(i) == '?') && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    // 正则表达式匹配
    public boolean isMatch2(String s, String p) {
        int m = s.length();
        int n = p.length();
        s = " " + s;
        p = " " + p;
        // 创建 dp 表
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 初始化
        dp[0][0] = true;
        for(int j = 2; j <= n; j += 2) {
            if (p.charAt(j) == '*') {
                dp[0][j] = true;
            } else {
                break;
            }
        }
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                //  System.out.println("s[i]:" + s.charAt(i) + " p[j]: " + p.charAt(j));
                if (p.charAt(j) == '*') {
                    dp[i][j] = dp[i][j - 2] || ((p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i)) && dp[i - 1][j]);
                    //   System.out.println("i: " + i + " j: " + j + " dp[i][j]: " + dp[i][j]);
                } else {
                    dp[i][j] = (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.') && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    // 交错字符串
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;
        // 创建 dp 表
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 初始化
        dp[0][0] = true;
        for(int i = 1; i <= m; i++) {
            if(s1.charAt(i) == s3.charAt(i)) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        for(int j = 1; j <= n; j++) {
            if (s2.charAt(j) == s3.charAt(j)) {
                dp[0][j] = true;
            } else {
                break;
            }
        }
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                // System.out.println("i: " + i + " j: " + j + " dp[i - 1][j]: " + dp[i - 1][j] + " dp[i][j - 1]: " + dp[i][j - 1]);
                // if (s1.charAt(i) == s3.charAt(i + j)) {
                //     dp[i][j] = dp[i - 1][j];
                // } else if(s2.charAt(j) == s3.charAt(i +j)) {
                //     dp[i][j] = dp[i][j - 1];
                // }
                dp[i][j] = ((s1.charAt(i) == s3.charAt(i + j) && dp[i - 1][j] == true)
                        || (s2.charAt(j) == s3.charAt(i +j) && dp[i][j - 1] == true));
                //  System.out.println("i: " + s1.charAt(i) + " j: " + s2.charAt(j) + " i + j:" + s3.charAt(i + j) + " dp[i][j]: " + dp[i][j]);
            }
        }
        return dp[m][n];
    }

    // 两个字符串的最小ASCII删除和
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        s1 = " " + s1;
        s2 = " " + s2;
        // 创建 dp 表
        int[][] dp = new int[m+1][n+1];
        // 初始化
        for(int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i);
        }
        for(int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j);
        }
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i), dp[i][j - 1] + s2.charAt(j));
                }
            }
        }
        return dp[m][n];
    }

    // 最长重复子数组
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 创建 dp 表
        int[][] dp = new int[m + 1][n + 1];
        // 初始化
        int ret = 0;
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
                //else {
                //     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                // }
                // System.out.println("i: " + i + " nums1[i]: " + nums1[i - 1] + " j: " + j + " nums2[j]: " + nums2[j - 1]);
                // System.out.println("dp[i][j]: " + dp[i][j]);
            }
        }
        return ret;
    }

    // 01背包（不需要恰好装满）
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        // 创建 dp 表
        int[][] dp = new int[n + 1][V + 1];
        // 初始化
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - vw[i - 1][0] >= 0) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i - 1][j - vw[i-1][0]] + vw[i - 1][1]);
                }
            }
        }
        return dp[n][V];
    }

    // 01背包问题（不需要恰好装满 + 需要恰好装满）
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();
        int[][] vw = new int[n][2];
        for(int i = 0; i < n; i++) {
            vw[i][0] = scanner.nextInt();
            vw[i][1] = scanner.nextInt();
        }
        // 创建 dp 表
        int[][] dp1 = new int[n + 1][v + 1];
        int[][] dp2 = new int[n + 1][v + 1];
        // 初始化
        for(int j = 1; j <= v; j++) {
            dp2[0][j] = -1;
        }
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= v; j++) {
                dp1[i][j] = dp1[i - 1][j];
                dp2[i][j] = dp2[i - 1][j];
                if (j - vw[i - 1][0] >= 0) {
                    dp1[i][j] = Math.max(dp1[i][j],
                            dp1[i - 1][j - vw[i-1][0]] + vw[i-1][1]);
                    if (dp2[i-1][j-vw[i-1][0]] != -1) {
                        dp2[i][j] = Math.max(dp2[i][j],
                                dp2[i-1][j-vw[i-1][0]] + vw[i-1][1]);
                    }
                }
            }
        }
        System.out.println(dp1[n][v]);
        if (dp2[n][v] == -1) {
            dp2[n][v] = 0;
        }
        System.out.println(dp2[n][v]);
    }

    // 01背包问题 + 滚动数组优化
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();
        int[][] vw = new int[n][2];
        for(int i = 0; i < n; i++) {
            vw[i][0] = scanner.nextInt();
            vw[i][1] = scanner.nextInt();
        }
        // 创建 dp 表
        // int[][] dp1 = new int[n + 1][v + 1];
        int[] dp1 = new int[v + 1];
//         int[][] dp2 = new int[n + 1][v + 1];
        int[] dp2 = new int[v + 1];
        // 初始化
        for(int j = 1; j <= v; j++) {
            dp2[j] = -1;
        }
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = v; j >= 0; j--) {
//                 dp1[j] = dp1[i - 1][j];
//                 dp2[i][j] = dp2[i - 1][j];
                if (j - vw[i - 1][0] >= 0) {
                    dp1[j] = Math.max(dp1[j],
                            dp1[j - vw[i-1][0]] + vw[i-1][1]);
                    if (dp2[j-vw[i-1][0]] != -1) {
                        dp2[j] = Math.max(dp2[j],
                                dp2[j-vw[i-1][0]] + vw[i-1][1]);
                    }
                }
            }
        }
        System.out.println(dp1[v]);
        if (dp2[v] == -1) {
            dp2[v] = 0;
        }
        System.out.println(dp2[v]);
    }

    // 分割等和子集
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) {
            return false;
        }
        // 创建 dp 表
        boolean[] dp = new boolean[sum / 2 + 1];
        dp[0] = true;
        for(int i = 1; i <= n; i++) {
            for(int j = sum / 2; j > 0; j--) {
                if(j - nums[i - 1] >= 0) {
                    dp[j] = dp[j] || dp[j - nums[i - 1]];
                }
            }
        }
        return dp[sum / 2];
    }

    // 目标和
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum += nums[i];
        }
        int k = (sum + target) / 2;
        if ((sum + target) % 2 != 0 || k < 0) {
            return 0;
        }
        // 创建 dp 表
        int[] dp = new int[k + 1];
        // 初始化
        dp[0] = 1;
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = k; j >= 0; j--) {
                if (j - nums[i - 1] >= 0) {
                    dp[j] += dp[j - nums[i - 1]];
                }
            }
        }
        return dp[k];
    }

    // 最后一块石头的重量II
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum += stones[i];
        }
        int t = sum / 2;
        // 创建 dp 表
        int[] dp = new int[t + 1];
        // 初始化
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = t; j >= 0; j--) {
                if (j - stones[i - 1] >= 0) {
                    dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
                }
            }
        }
        return (sum - 2 * dp[t]);
    }

    // 完全背包（无需装满 + 需恰好装满）
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int v = in.nextInt();
        int[][] vw = new int[n+1][2];
        for(int i = 1; i <= n; i++) {
            vw[i][0] = in.nextInt();
            vw[i][1] = in.nextInt();
        }
        // 创建 dp 表
        int[][] dp1 = new int[n+1][v+1];
        int[][] dp2 = new int[n+1][v+1];
        // 初始化
        for(int j = 1; j <= v; j++) {
            dp2[0][j] = -1;
        }
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= v; j++) {
                dp1[i][j] = dp1[i - 1][j];
                dp2[i][j] = dp2[i - 1][j];
                if (j - vw[i][0] >= 0) {
                    dp1[i][j] = Math.max(dp1[i][j],
                            dp1[i][j - vw[i][0]] + vw[i][1]);
                    if (dp2[i][j-vw[i][0]] != -1) {
                        dp2[i][j] = Math.max(dp2[i][j],
                                dp2[i][j - vw[i][0]] + vw[i][1]);
                    }
                }
                //   System.out.println("i:" + i + " j: " + j + " dp2[i][j]: " + dp2[i][j]);
            }
        }
        // 返回
        if (dp2[n][v] == -1) {
            dp2[n][v] = 0;
        }
        System.out.println(dp1[n][v]);
        System.out.println(dp2[n][v]);
    }

    // 完全背包 + 滚动数组优化
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int v = in.nextInt();
        int[][] vw = new int[n+1][2];
        for(int i = 1; i <= n; i++) {
            vw[i][0] = in.nextInt();
            vw[i][1] = in.nextInt();
        }
        // 创建 dp 表
        int[]  dp1 = new int[v+1];
        int[] dp2 = new int[v+1];
        // 初始化
        for(int j = 1; j <= v; j++) {
            dp2[j] = -1;
        }
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= v; j++) {
                //dp1[j] = dp1[i - 1][j];
                // dp2[i][j] = dp2[i - 1][j];
                if (j - vw[i][0] >= 0) {
                    dp1[j] = Math.max(dp1[j],
                            dp1[j - vw[i][0]] + vw[i][1]);
                    if (dp2[j-vw[i][0]] != -1) {
                        dp2[j] = Math.max(dp2[j],
                                dp2[j - vw[i][0]] + vw[i][1]);
                    }
                }
                //   System.out.println("i:" + i + " j: " + j + " dp2[i][j]: " + dp2[i][j]);
            }
        }
        // 返回
        if (dp2[v] == -1) {
            dp2[v] = 0;
        }
        System.out.println(dp1[v]);
        System.out.println(dp2[v]);
    }

    // 零钱兑换
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        // 创建 dp 表
        int[] dp = new int[amount + 1];
        // 初始化
        int INF =  0x3f3f3f3f;
        for(int j = 1; j <= amount; j++) {
            dp[j] = INF;
        }
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= amount; j++) {
                if (j - coins[i - 1] >= 0) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
                }
            }
        }
        return dp[amount] >= INF ? -1: dp[amount];
    }

    // 零钱兑换II
    public int change(int amount, int[] coins) {
        int n = coins.length;
        // 创建 dp 表
        int[] dp = new int[amount + 1];
        // 初始化
        dp[0] = 1;
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= amount; j++) {
                if(j - coins[i - 1] >= 0) {
                    dp[j] += dp[j - coins[i - 1]];
                }
            }
        }
        return dp[amount];
    }

    // 完全平方数
    public int numSquares(int n) {
        int m = (int)Math.sqrt(n);
        // 创建 dp 表
        int[] dp = new int[n + 1];
        // 初始化
        int INF = 0x3f3f3f3f;
        for(int i = 1; i <= n; i++) {
            dp[i] = INF;
        }
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if (j - i * i >= 0) {
                    dp[j] = Math.min(dp[j], dp[j - i*i] + 1);
                }
            }
        }
        return dp[n];
    }

    // 一和零
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        // 创建 dp 表
        int[][] dp = new int[m + 1][n + 1];
        // int INF = 0x3f3f3f3f;
        // 初始化
        // for(int i = 0; i <= m; i++) {
        //     for(int j = 0; j <= n; j++) {
        //         dp[i][j] = -INF;
        //     }
        // }
        // dp[0][0] = 0;
        // 填表
        for(int i = 1; i <= len; i++) {
            int[] nums = count(strs[i - 1]);
            for(int j = m; j >= nums[0]; j--) {
                for(int k = n; k >= nums[1]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - nums[0]][k - nums[1]] + 1);
                }
            }
        }
        // 返回
        return dp[m][n];
    }

    public int[] count(String str) {
        int[] ret = new int[2];
        if (str.length() == 0) {
            return ret;
        }
        for(int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                ret[0]++;
            } else {
                ret[1]++;
            }
        }
        return ret;
    }

    // 盈利计划
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        // 创建 dp 表
        int[][] dp = new int[n + 1][minProfit + 1];
        // 初始化
        for(int j = 0; j <= n; j++) {
            dp[j][0] = 1;
        }
        // 填表
        for(int i = 1; i <= len; i++) {
            for(int j = n; j >= group[i - 1]; j--) {
                for(int k = minProfit; k >= 0; k--) {
                    dp[j][k] += dp[j - group[i - 1]][Math.max(0, k - profit[i - 1])];
                    dp[j][k] %= 1000000000 + 7;
                }
            }
        }
        // 返回
        return dp[n][minProfit];
    }

    // 组合总数IV
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        // 创建 dp 表
        int[] dp = new int[target + 1];
        // 初始化
        dp[0] = 1;
        // 填表
        for(int i = 1; i <= target; i++) {
            for(int x: nums) {
                if (i - x >= 0) {
                    dp[i] += dp[i - x];
                }
            }
        }
        // 返回
        return dp[target];
    }

    // 不同的二叉搜索树
    public int numTrees(int n) {
        // 创建 dp 表
        int[] dp = new int[n + 1];
        // 初始化
        dp[0] = 1;
        // 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[i - j] * dp[j - 1];
            }
        }
        return dp[n];
    }
}
